题解 P2050 【[NOI2012]美食节】

发表于 | 更新于

$Description$

有$n$个厨师$m$道菜，每种菜有$p_i$个人点，每个厨师$j$烧第$i$道菜要$t_{i,j}$分钟，所有人等菜时间之和为多少？

$Solution$

P2053 [SCOI2007]修车的加强版

我们就按照那题的方法建图

对于每个菜$i$

$S \stackrel{p_{i}, 0}{\longrightarrow}i$

然后建$n$层点，每层点有$m$个点，第$i$层的第$j$个点表示第$j$个厨师做第倒数$i$道菜,记为$c_{i,j}$。

$c_{i,j} \stackrel{1, 0}{\longrightarrow}t$

假设第$j$个厨师做第倒数$k$道菜，那么对于菜$i$，向其连一条流量为$1$，费用为$k\times t_{i,j}$的边。这表示第$j$个厨师做的倒数第$k$道菜是菜$i$，那么就要做$t_{i,j}$这么长的时间，有$k$个人要等这么长的时间。

$i \stackrel{1,k\times t_{i,j}}{\longrightarrow}c_{j,k}$

然后，我们会发现，这样写会$T$成傻$*$

然后我们就必须进行优化

我们发现一个性质，如果经过$c_{i,j}$的流为$0$,那么经过$c_{i+1,j}\sim c_{n,j}$的流也一定为$0$.也就是说这些点根本不用建。

于是我们先建$n$个菜和第一层点，并连接第一层点和$t$,跑一边$spfa$

一旦一条增广路被用掉了（也就是$c_{j,k}$被用掉了），那么我们就把$c_{j,k+1}$加上去，再跑$spfa$

所以我们考虑用$EK$写费用流，因为$EK$一次只找一条增广路，与题意相符，且跑费用流的效率和$Dinic$差不多快(我也不知道为什么)。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define pb push_back
#define N 400000
using namespace std;
struct edge{
    int to,dis,w,next;
}e[1007000];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int cr,flow[N],lxy=1,pri[N],pre[N],ma[500][500],a[N],p,w[N],cnt=1,head[N],dis[N],inque[N],vis[N],cur[N],cost,n,m,s,t;
inline void add(int u,int v,int d,int w){
    e[++cnt].to=v;
    e[cnt].dis=d;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
    e[++cnt].to=u;
    e[cnt].dis=0;
    e[cnt].w=-w;
    e[cnt].next=head[v];
    head[v]=cnt;
}
inline int id(int x,int y){
    return n+(x-1)*p+y;
}
inline int chushi(int k){
    return (k-n-1)/p+1;
}
inline int waittime(int k){
    return (k-n-1)%p+1;
}
bool spfa(){
    queue<int>q;
    q.push(s);memset(flow,0x3f,sizeof(flow));
    memset(dis,0x3f,sizeof(dis));dis[s]=0;
    while (!q.empty()){
        int u=q.front();q.pop();inque[u]=0;
        for (int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if (e[i].dis&&dis[v]>dis[u]+e[i].w){
                dis[v]=dis[u]+e[i].w;
                pre[v]=u;pri[v]=i;flow[v]=min(flow[u],e[i].dis);
                if (!inque[v])
                    q.push(v),inque[v]=1;
            }
        }
    }
    return dis[t]!=inf;
}
inline int mcmf(){
    int res=0;
    while (spfa()){
        res+=flow[t];
        cost+=flow[t]*dis[t];
        for (int now=t;now!=s;now=pre[now]){
            e[pri[now]].dis-=flow[t];
            e[pri[now]^1].dis+=flow[t];
        }
        int lxy=pre[t];
        add(lxy+1,t,1,0);//向终点连边 
        for (int i=1;i<=n;++i){++cr;
            add(i,lxy+1,1,ma[i][chushi(lxy+1)]*waittime(lxy+1));
        }
    }
    return res;
}
signed main(){
    n=read(),m=read();
    for (int i=1;i<=n;++i)w[i]=read(),p+=w[i],add(s,i,w[i],0);
    s=0,t=n+p*m+1;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j){ 
            ma[i][j]=read();
            add(i,id(j,1),1,ma[i][j]);
        } 
    for (int i=1;i<=m;++i)
        add(id(i,1),t,1,0);
    mcmf();
    printf("%d\n",cost);
    return 0;
}